package net.xuele.learn.dancing.dp;

/**
 * @Author: yubo
 * @date: 14:57 2020/12/29
 * @Description: 类描述：最长回文子序列
 * 注意区分最长上升子序列的问题！！！那个里面dp数组是一维的
 */

public class LongestPalindromeSubseq {

    public int longestPalindromeSubseq(String s) {
        // 在子串s[i..j]中，最长回文子序列的长度为dp[i][j]
        // 找状态转移需要归纳思维，说白了就是如何从已知的结果推出未知的部分
        // 要求dp[i][j]，如果已经知道子问题dp[i+1][j-1]
        // （此时，s[i+1]不一定等于s[j-1]，这表示的s[i+1..j-1]中的最长回文子串），就方便很多了
        // 如果s[i] = s[j]，那很明显，最长回文子序列就是dp[i+1][j-1]+2了
        // 如果s[i] != s[j]，则需要区别对待了
        int length = s.length();
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            // i == j 的时候只有一个字符
            dp[i][i] = 1;
        }
        for (int i = length - 1; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                // 状态转移方程
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][length - 1];
    }
}
